Core (graph theory)

In the mathematical field of graph theory, a core is a notion that describes behavior of a graph with respect to graph homomorphisms.

Contents

1 Definition
2 Examples
3 Properties
4 See also
5 References

Definition

Graph $G$ is a core if every homomorphism $f:G \to G$ is an isomorphism, that is it is a bijection of vertices of $G$ .
A core of a graph $H$ is a graph $G$ such that

There exists a homomorphism from $H$ to $G$ ,
there exists a homomorphism from $G$ to $H$ , and
$G$ is minimal with this property.

Examples

Any complete graph is a core.
A cycle of odd length is a core.
A core of a cycle of even length is $K_2$ .

Properties

Core of a graph is determined uniquely, up to isomorphism.
If $G \to H$ and $H \to G$ then the graphs $G$ and $H$ have isomorphic cores.

See also

the k-core of a graph, obtained by iteratively removing all vertices of degree at most k, is a different notion.

References

Godsil, Chris, and Royle, Gordon. Algebraic Graph Theory. Graduate Texts in Mathematics, Vol. 207. Springer-Verlag, New York, 2001. Chapter 6 section 2.